テンプレートには自分で試したことという項目があります.すなわち回答者がまるまる答えを教えてくれるわけではないので,丸投げのような形で質問するのはやめましょう.
あと明らかに出力例と問題文の条件に齟齬があるので,質問の投稿前にプレビューして確認してください.
Like!
java 教えてください
Q&AClosed
javaの問題をしていますが全然わかりません
1～7の2枚ずつのカード14枚を使って以下の条件になるように、隙間なく並べられるすべてのパターンを調べるプログラムを作成してください。 なお、左右反転しただけのパターンは除外する。
条件
1と1のカードの間には1枚のカードが入る。
2と2のカードの間には2枚のカードが入る。
3と3のカードの間には2枚のカードが入る。
4と4のカードの間には2枚のカードが入る。
5と5のカードの間には2枚のカードが入る。
6と6のカードの間には2枚のカードが入る。
7と7のカードの間には7枚のカードが入る。
実行結果
①⑦①②⑤⑥②③④⑦⑤③⑥④
①⑦①②⑥④②⑤③⑦④⑥③⑤
①⑥①⑦②④⑤②⑥③④⑦⑤③
①⑤①⑥⑦②④⑤②③⑥④⑦③
①④①⑤⑥⑦④②③⑤②⑥③⑦
①④①⑥⑦③④⑤②③⑥②⑦⑤
①⑥①③⑤⑦④③⑥②⑤④②⑦
①⑤①⑦③④⑥⑤③②④⑦②⑥
①⑤①⑥③⑦④⑤③②⑥④②⑦
①⑤①④⑥⑦③⑤④②③⑥②⑦
⑤①⑦①⑥②⑤④②③⑦⑥④③
④①⑦①⑥④②⑤③②⑦⑥③⑤
④①⑥①⑦④③⑤②⑥③②⑦⑤
⑦①③①⑥④③⑤⑦②④⑥②⑤
⑦①④①⑥③⑤④⑦③②⑥⑤②
⑥①⑤①⑦③④⑥⑤③②④⑦②
④⑥①⑦①④⑤②⑥③②⑦⑤③
⑦③①⑥①③④⑤⑦②⑥④②⑤
④⑥①⑦①④③⑤⑥②③⑦②⑤
⑤⑥①⑦①③⑤④⑥③②⑦④②
⑦④①⑤①⑥④③⑦⑤②③⑥②
⑤⑦①④①⑥⑤③④⑦②③⑥②
③⑥⑦①③①④⑤⑥②⑦④②⑤
⑤⑦④①⑥①⑤④③⑦②⑥③②
②⑥⑦②①⑤①④⑥③⑦⑤④③
④⑤⑥⑦①④①⑤③⑥②⑦③②
全部で26通りでした。
0
3Answer
2
これはJAVAの問題ではなく、アルゴリズムの問題ですね。
アルゴリズムを考える力はプログラマーの大事な基礎力です。
どうか諦めずに挑戦してみてください。
Like!
Javaというより、アルゴリズムの問題ですね。
解き方はいくつもあると思いますが、深さ優先探索で解いてみました。
言語はSwiftです。Javaコードは後ほどアップします。
import Foundation
let main: () = {
let K = [
[1, 0, 1],
[2, 0, 0, 2],
[3, 0, 0, 0, 3],
[4, 0, 0, 0, 0, 4],
[5, 0, 0, 0, 0, 0, 5],
[6, 0, 0, 0, 0, 0, 0, 6],
[7, 0, 0, 0, 0, 0, 0, 0, 7],
]
func isPlaceable(_ n: Int, _ p: Int, _ g: inout [Int]) -> Bool {
let k = K[n]
if p + k.count > g.count { return false }
for m in 0 ..< k.count {
if k[m] != 0 {
if g[p + m] != 0 { return false }
g[p + m] = k[m]
}
}
return true
}
var ans = Set<[Int]>()
func dfs(_ n: Int, _ g: [Int]) {
if n == 7 {
if !ans.contains(g.reversed()) {
ans.insert(g)
}
return
}
for p in 0 ..< g.count {
var g = g
if !isPlaceable(n, p, &g) { continue }
dfs(n + 1, g)
}
}
dfs(0, [Int](repeating: 0, count: 14))
ans.sorted{ $0.lexicographicallyPrecedes($1) }.forEach {
$0.forEach { print($0, terminator: " ") }
print()
}
}()
Like!
Comments
上のSwiftコードをChatGPTにJavaに変換してもらったコードです。
import java.util.HashSet; import java.util.Set; public class Main { static int[][] K = { {1, 0, 1}, {2, 0, 0, 2}, {3, 0, 0, 0, 3}, {4, 0, 0, 0, 0, 4}, {5, 0, 0, 0, 0, 0, 5}, {6, 0, 0, 0, 0, 0, 0, 6}, {7, 0, 0, 0, 0, 0, 0, 0, 7} }; static boolean isPlaceable(int n, int p, int[] g) { int[] k = K[n]; if (p + k.length > g.length) return false; for (int m = 0; m < k.length; m++) { if (k[m] != 0) { if (g[p + m] != 0) return false; g[p + m] = k[m]; } } return true; } static Set<int[]> ans = new HashSet<>(); static void dfs(int n, int[] g) { if (n == 7) { if (!ans.contains(reverse(g))) { ans.add(g); } return; } for (int p = 0; p < g.length; p++) { int[] clonedG = g.clone(); if (!isPlaceable(n, p, clonedG)) continue; dfs(n + 1, clonedG); } } static int[] reverse(int[] array) { int[] reversedArray = new int[array.length]; for (int i = 0; i < array.length; i++) { reversedArray[i] = array[array.length - 1 - i]; } return reversedArray; } public static void main(String[] args) { dfs(0, new int[14]); ans.stream().sorted((a, b) -> { for (int i = 0; i < a.length; i++) { if (a[i] != b[i]) return a[i] - b[i]; } return 0; }).forEach(g -> { for (int i : g) { System.out.print(i + " "); } System.out.println(); }); } }実行してみると、左右反転の除外が効いていないです。なぜ？
自己レスです。
実行してみると、左右反転の除外が効いていないです。なぜ？
if (!ans.contains(reverse(g))) {
↑この場合、containsメソッドを使うなら、hashCodeメソッドとequalsメソッドを実装する必要があるようです。
そこで、int[]やめてStringで実装しました。import java.util.HashSet; import java.util.Set; import java.util.Arrays; import java.util.Collections; public class Main { static String[] K = { "101", "2002", "30003", "400004", "5000005", "60000006", "700000007" }; static boolean isPlaceable(int n, int p, String g) { String k = K[n]; if (p + k.length() > g.length()) return false; for (int m = 0; m < k.length(); m++) { if (k.charAt(m) != '0') { if (g.charAt(p + m) != '0') return false; } } return true; } static String place(int n, int p, String g) { String k = K[n]; if (p + k.length() > g.length()) return g; for (int m = 0; m < k.length(); m++) { if (k.charAt(m) != '0') { if (g.charAt(p + m) != '0') return g; } } String s = ""; for (int m = 0; m < g.length(); m++) { if (p <= m && m < p + k.length()) { if (k.charAt(m - p) != '0') { s += k.charAt(m - p); } else { s += g.charAt(m); } } else { s += g.charAt(m); } } return s; } static String reverse(String aString) { if (aString == null) return aString; String reverseString = ""; for (int i = aString.length() - 1; i >= 0; i--) { reverseString = reverseString + aString.charAt(i); } return reverseString; } static Set<String> ans = new HashSet<>(); static void dfs(int n, String g) { if (n == 7) { if (!ans.contains(reverse(g))) { ans.add(g); } return; } for (int p = 0; p < g.length(); p++) { if (!isPlaceable(n, p, g)) continue; String nextG = place(n, p, g); dfs(n + 1, nextG); } } public static void main(String[] args) { dfs(0, "00000000000000"); String array[] = ans.toArray(String[]::new); Arrays.sort(array); for (String s : array) { System.out.println(s); }; } }